#!/usr/bin/python2.4
## Copyright 2010 Google Inc.

# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""Implementation of two-archive evolutionary algorithm.

This is an implementation of Two-Archive multi-objective evolutionary
algorithm by Praditwong and Yao (DOI: 10.1109/ICCIAS.2006.294139).
It maintains two separate archives for convergence and diversity
of the population.

The main iteration stops when:
    1) it consumes all the given fitness evaluations, or
    2) the archives do not change for 5 consecutive iterations
       (i.e. we assume that the algorithm has converged)

Instead of random initialisation of the population, the module uses
what is called spread-betting. This is to ensure that the randomisation
is achieved in the phenotype space rather than genotype space (i.e. we
ensure that the population will also include sets of tests that only
achieves low coverage - diversity is important!).
"""

__author__ = 'ntrolls@gmail.com (Shin Yoo)'

import operator
import random

import distance
import numpy
import solution


class TwoArchive(object):
  """Implementation of the Two-Archive algorithm."""

  def __init__(self, prob):
    self.problem = prob
    self.properties = {}

    self.c_archive = set()
    self.d_archive = set()

    self.population = []
    self.offspringpopulation = []

  def Execute(self):
    """Starts the evolutionary iteration."""
    self.populationsize = self.properties['populationSize']
    self.archivesize = self.properties['archiveSize']
    self.maxevaluations = self.properties['maxEvaluations']

    self.selection = self.properties['selection']
    self.crossover = self.properties['crossover']
    self.mutation = self.properties['mutation']

    evaluations = 0

    self.population = self.Spreadbet(self.populationsize)
    generation = 0
    lastmodification = 0
    while(evaluations < self.maxevaluations and
          generation - lastmodification < 5):
      print '%d evaluations remaining...' % (self.maxevaluations - evaluations)
      if self.CollectNonDominatedIndividuals():
        lastmodification = generation
        print 'current generation:%d, last modification:%d' % (generation,
                                                               lastmodification)
      self.offspringpopulation = []
      while len(self.offspringpopulation) < len(self.population):
        if evaluations < self.maxevaluations:
          #select
          parents = self.selection.Execute(self.c_archive, self.d_archive)

          #crossover
          offsprings = self.crossover.Execute(parents)

          #mutate
          self.mutation.Execute(offsprings[0])
          self.mutation.Execute(offsprings[1])

          #evaluate
          self.problem.Evaluate(offsprings[0])
          self.problem.Evaluate(offsprings[1])

          #append to the population pool
          self.offspringpopulation.append(offsprings[0])
          self.offspringpopulation.append(offsprings[1])

          evaluations += 2
      self.population = self.offspringpopulation
      generation += 1
    self.CollectNonDominatedIndividuals()
    return set(self.c_archive).union(set(self.d_archive))

  def CollectNonDominatedIndividuals(self):
    """Collect solutions to be added to archives."""
    modified = False
    for i in xrange(len(self.population)):
	  ## Consider each individual in population
      individual = self.population[i]
      ## If the individual is already in archive, continue
      if individual in self.c_archive or individual in self.d_archive:
        continue
      ## If the individual is not dominated by population and archives
      if ((not individual.DominatedBy(set(self.population))) and
          (individual not in self.c_archive.union(self.d_archive))):
        if ((not individual.DominatedBy(self.c_archive)) and
            (not individual.DominatedBy(self.d_archive))):
          ## If there are solutions in archives that are dominated by individual
          ## we remove the dominated solutuions from the archives
          individual.dFlag = False
          dominatedin_c = individual.GetSolutionsDominatedByThis(self.c_archive)
          dominatedin_d = individual.GetSolutionsDominatedByThis(self.d_archive)

          if dominatedin_c or dominatedin_d:
            individual.dFlag = True
            self.c_archive = self.c_archive.difference(dominatedin_c)
            self.d_archive = self.d_archive.difference(dominatedin_d)

          ## If the individual dominated any solution in archive, add it to
	        ## the convergence archive; otherwise, add it to diversity archive
          if individual.dFlag:
            self.c_archive.add(individual)
            modified = True
          else:
            self.d_archive.add(individual)
            modified = True
    ## If archives outgrow the predefined size, we prune the diversity
    ## archive, strating from the one that is closest to the solutions
    ## in the convergency archive, one by one until the size fits
    if len(self.c_archive) + len(self.d_archive) > self.archivesize:
      dist = distance.Distance()
      d_archivelist = []
      for sol in self.d_archive:
        sol.distance = dist.DistanceToSolutionSet(sol, self.c_archive)
        d_archivelist.append(sol)
      d_archivelist.sort(key=operator.attrgetter('distance'))
      while len(self.c_archive) + len(d_archivelist) > self.archivesize:
        d_archivelist = d_archivelist[1:]
      self.d_archive = set(d_archivelist)
    return modified

  def Spreadbet(self, popsize, stepsize=10):
    """Initialises the population pool so that solutions are evenly spread."""
    pop = []
    while len(pop) < popsize:
      for i in xrange(stepsize):
        g = numpy.zeros(self.problem.numberoftests, dtype=bool)
        for j in xrange(len(g)):
          g[j] = random.random() < (1.0 / stepsize * i)
        if len(pop) < popsize:
          s = solution.Solution(self.problem, gene=g)
          self.problem.Evaluate(s)
          pop.append(s)
        else:
          break
    return pop
